1. Field of the Invention
This invention relates to computer database systems; and more specifically to a method for optimizing queries, updates and transactions in a distributed database system.
2. Description of the Prior Art
Modern database systems are frequently distributed, meaning that the data is kept at widely dispersed locations. Several different computers control access to different parts of the data, and several computers are used to interface with users at different locations; these may or may not be the same machines that access the data itself. The various computers are connected by communications links, and it is normal for these links to be relatively low speed, compared with, say, the speed at which a file can be read off of a disk. The consequence of this assumption about communication is that the transfer of data between computers becomes a bottleneck, and most of the issues unique to distributed systems concern ways of dealing with this bottleneck.
A distributed database consists of a number of sites, each of which is a computer and a facility for storing data. In general, each site has both a transaction server to process queries and updates generated by a user, and a file server to handle data access. However, it is possible that one of these two functions is missing at any particular site, and often one computer will act as both the transaction and file server.
A database is composed of "items", which are individually lockable pieces of data. It is a possibility that some items are duplicated, in the sense that they appear at two or more sites. The reason for doing so is that accesses to frequently read items may be sped up if the item is available at the same site that processed the read request. Further, the redundant storage of items makes it less likely that the item will be lost in a crash. The penalty is that more messages must be sent to update or lock a duplicated item than an item that appears only once.
Some or all pairs of sites are connected by links, over which messages can be sent and data transmitted. Based on the technology of the early 1980's, the time to send even a short message between geographically distributed sites is nontrivial, say 0.1 seconds, and the rate at which data can be transmitted across a link is not too great, perhaps around 10,000 bytes per second or less. The tenth of a second overhead to send a message represents the time for the two processors connected by a link to execute the protocol necessary for one to send a message, assured that the other will receive it and know what to do with it. The shipping rate for data is limited by the speed at which a processor can send or receive data, or the bandwidth of the link (rate at which data can be transmitted across the line) or both.
A prior art system which optimizes queries in a distributed database system is System R*. System R* is the experimental extension of System R to the distributed environment. Like its parent, it performs optimization in an exhaustive way, confident that the cost of considering many strategies will pay off in lower execution costs for queries, especially for queries that are compiled and used many times.
The optimization method of System R* applies to an algebraic query, where the expression to be optimized represents the query applied to logical relations, which in turn are expressed in terms of physical relations. The operators assumed to appear in the query are the usual select, project, join and union, plus a new operator choice, which represents the ability of the system to choose any of the identical, replicated copies of a given relation. The System R* method of optimization considers all ways to evaluate the nodes of the compacted tree, taking into account
1. the various orders in which an operator like union or join of many relations can be performed as a sequence of binary steps,
2. the various sites at which each node of the tree could have its result computed, and
3. several different ways that the join could be computed.
When the System R* method considers each of the options listed above, it must evaluate the cost of these methods. The actual cost function used in System R* is quite complex, it takes account of the computation cost at a site as well as the transmission cost between sites. Further, the System R* method for optimizing distributed queries exhaustively considers all possible strategies for query evaluation that can be built from a fixed collection of options. The System R* is described in greater detail in Principles of Database Systems, by Jeffrey D. Ullman, Computer Science Press, 1982, which is incorporated herein by reference.
The System R* method has the disadvantage that the computation time spent in determining an optimum query execution strategy may exceed the time to be saved by execution of the optimal strategy. Further, the System R* method requires the site at which optimization is being performed to have access to sufficient information about the various sites so that the computation cost at the sites can be calculated. This site information has to be transmitted to the optimization site and must be updated as conditions at the various sites change. In addition, the System R* optimization method requires that all, global and local, optimization must be performed before any execution of the query can be started.